package com.aqie.hard.slidingWindow;



import com.aqie.structure.Pair;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * todo
 * 76 最小覆盖子串 在字符串 S 里面找出：包含 T 所有字母的最小子串
 * 滑动窗口算法：
 *  1. 初始,left, right 都指向S第一个元素
 *  2. right指针右移, 直到得到一个可行窗口
 *  3. 得到可行窗口后， 将left指针右移，若窗口依然可行,更新最小窗口大小
 *  4. 窗口不再可行， 跳转至2
 */
public class MinWindow {
    /**
     * 滑动窗口，双指针 ： 77ms
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";

        Map<Character, Integer> dictT = new HashMap<>();
        for (int i = 0; i < t.length(); i++){
            dictT.put(t.charAt(i), dictT.getOrDefault(t.charAt(i), 0) + 1);
        }

        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;

        Map<Character, Integer> windowsCounts = new HashMap<>();
        int[] ans = {-1, 1, 0};
        while (r < s.length()){
            char c = s.charAt(r);
            windowsCounts.put(s.charAt(r), windowsCounts.getOrDefault(c, 0) + 1);

            if (dictT.containsKey(c) && windowsCounts.get(c).intValue() == dictT.get(c).intValue()){
                formed++;
            }

            while (l <= r && formed == required){
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]){
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowsCounts.put(c, windowsCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowsCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;

            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }

    /**
     * O(2 * |filtered_S| + |S| + |T|)  106ms
     * @param s
     * @param t
     * @return
     */
    public String minWindow1(String s, String t) {

        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<Character, Integer>();

        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

        int required = dictT.size();

        // Filter all the characters from s into a new list along with their index.
        // The filtering criteria is that the character should be present in t.
        List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dictT.containsKey(c)) {
                filteredS.add(new Pair<Integer, Character>(i, c));
            }
        }

        int l = 0, r = 0, formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
        int[] ans = {-1, 0, 0};

        // Look for the characters only in the filtered list instead of entire s.
        // This helps to reduce our search.
        // Hence, we follow the sliding window approach on as small list.
        while (r < filteredS.size()) {
            char c = filteredS.get(r).getValue();
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            // Try and co***act the window till the point where it ceases to be 'desirable'.
            while (l <= r && formed == required) {
                c = filteredS.get(l).getValue();

                // Save the smallest window until now.
                int end = filteredS.get(r).getKey();
                int start = filteredS.get(l).getKey();
                if (ans[0] == -1 || end - start + 1 < ans[0]) {
                    ans[0] = end - start + 1;
                    ans[1] = start;
                    ans[2] = end;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }



    /**
     * 数组优化 7ms
     * @param s
     * @param t
     * @return
     */
    public String minWindow2(String s, String t) {
        int[] map = new int[128];
        // 遍历字符串 t，初始化每个字母的次数
        for (int i = 0; i < t.length(); i++) {
            char char_i = t.charAt(i);
            map[char_i]++;
        }
        int left = 0; // 左指针
        int right = 0; // 右指针
        int ans_left = 0; // 保存最小窗口的左边界
        int ans_right = -1; // 保存最小窗口的右边界
        int ans_len = Integer.MAX_VALUE; // 当前最小窗口的长度
        int count = t.length();
        // 遍历字符串 s
        while (right < s.length()) {
            char char_right = s.charAt(right);

            // 当前的字母次数减一
            map[char_right]--;

            //代表当前符合了一个字母
            if (map[char_right] >= 0) {
                count--;
            }
            // 开始移动左指针，减小窗口
            while (count == 0) { // 如果当前窗口包含所有字母，就进入循环
                // 当前窗口大小
                int temp_len = right - left + 1;
                // 如果当前窗口更小，则更新相应变量
                if (temp_len < ans_len) {
                    ans_left = left;
                    ans_right = right;
                    ans_len = temp_len;
                }
                // 得到左指针的字母
                char key = s.charAt(left);
                // 因为要把当前字母移除，所有相应次数要加 1
                map[key]++;
                //此时的 map[key] 大于 0 了，表示缺少当前字母了，count++
                if (map[key] > 0) {
                    count++;
                }
                left++; // 左指针右移
            }
            // 右指针右移扩大窗口
            right++;
        }
        return s.substring(ans_left, ans_right + 1);
    }

    /**
     * 常规思路 74ms
     * @param s
     * @param t
     * @return
     */
    public static String minWindow3(String s, String t){
        int start = 0, minLen = Integer.MAX_VALUE;
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> needs = new HashMap<>();
        for (char c : t.toCharArray()){
            needs.put(c, needs.getOrDefault(c,0) + 1);
        }
        int match = 0;

        while (right < s.length()){
            char c1 = s.charAt(right);

            if (needs.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(needs.get(c1))) {
                    match++;
                }
            }

            right++;
            while (match == needs.size()){
                if (right- left < minLen){
                    // 更新最小子串位置和长度
                    start = left;
                    minLen = right - left;
                }
                char c2 = s.charAt(left);
                if (needs.containsKey(c2)){
                    window.put(c2, window.get(c2) - 1);
                    if (window.get(c2) < needs.get(c2)){
                        match--;
                    }
                }
                left++;
            }
        }
        // System.out.println(start + " " + minLen);
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);

    }

    public static void main(String[] args) {
        String S = "ADOBECODEBANC", T = "ABC";
        System.out.println(minWindow3(S, T));
    }
}
